# merge_sort.py

# low为左边已经排好序的开始索引，mid为其结束索引,high为右边已经排好序的最后一个元素索引
def merge(data, low, mid, high):
    i = low
    j = mid + 1
    temp = []  # 临时空间

    while i <= mid and j <= high: # 左右都没有越界
        if data[i] < data[j]:
            temp.append(data[i])
            i += 1
        else:
            temp.append(data[j])
            j += 1
    
    if i <= mid: # 左边有剩
        temp.extend(data[i:mid+1])
    
    if j <= high: # 右边有剩
        temp.extend(data[j:high+1])
    
    # 替换掉
    data[low:high+1] = temp
        

def merge_sort(data, low, high):
    if low < high: # 至少有两个元素
        mid = (low + high) // 2
        merge_sort(data, low, mid)
        merge_sort(data, mid+1, high)
        merge(data, low, mid, high)

    

import random
data = [random.randint(0, 100) for _ in range(100)]
print(data)
merge_sort(data, 0, len(data)-1)
print(data)